home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / dict / _pers_tree.c < prev    next >
C/C++ Source or Header  |  1994-11-16  |  25KB  |  1,147 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _pers_tree.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/impl/pers_tree.h>
  17.  
  18.  
  19. #define LEFT 0
  20. #define RIGHT 1
  21. #define f_isred(p)   ((p)->f_color)
  22. #define c_isred(p)   ((p)->c_color)
  23. #define f_mred(p)    ((p)->f_color=1)
  24. #define c_mred(p)    ((p)->c_color=1)
  25. #define f_mblack(p)  ((p)->f_color=0)
  26. #define c_mblack(p)  ((p)->c_color=0)
  27. #define f_lchild(p)  ((p)->f_link[0])
  28. #define c_lchild(p)  ((p)->c_link[0])
  29. #define f_rchild(p)  ((p)->f_link[1])
  30. #define c_rchild(p)  ((p)->c_link[1])
  31. #define f_parent(p)  ((p)->f_link[2])
  32. #define c_parent(p)  ((p)->c_link[2])
  33. #define f_isleaf(p)  (f_lchild(p)==(p))
  34. #define c_isleaf(p)  (c_lchild(p)==(p))
  35.  
  36.  
  37. void pers_rb_tree::f_rbclear(F_pers_tree_node* p)
  38. { if (!(f_isleaf(p)))
  39.     { f_rbclear(f_lchild(p));
  40.       f_rbclear(f_rchild(p));
  41.      }
  42.   delete p;
  43.  }
  44.  
  45. void pers_rb_tree::c_rbclear(C_pers_tree_node* p)
  46. { if (!(c_isleaf(p)))
  47.     { c_rbclear(c_lchild(p));
  48.       c_rbclear(c_rchild(p));
  49.      }
  50.   delete p;
  51. }
  52.  
  53.  
  54. F_pers_tree_node* pers_rb_tree::f_rbsearch(F_pers_tree_node* p, Version i)
  55. {
  56.   F_pers_tree_node *q;
  57.   
  58.   q = f_rchild(p);
  59.   while (!(f_isleaf(q)))
  60.   {  
  61.     if (i == q->ver_stamp || vless(i, q->ver_stamp))
  62.       q = f_lchild(q);
  63.     else
  64.       q = f_rchild(q);
  65.   }
  66.   return(q);
  67. }
  68.  
  69. C_pers_tree_node* pers_rb_tree::c_rbsearch(C_pers_tree_node* p, Version i)
  70. {
  71.   C_pers_tree_node *q;
  72.   
  73.   q = c_rchild(p);
  74.   while (!(c_isleaf(q)))
  75.   {
  76.     if (i == q->vers_stamp || vless(i, q->vers_stamp))
  77.       q = c_lchild(q);
  78.     else
  79.       q = c_rchild(q);
  80.   }
  81.   return(q);
  82. }
  83.  
  84. F_pers_tree_node * pers_rb_tree::f_nleaf(pers_tree_node* newvalue, Version i)
  85. {
  86.   F_pers_tree_node* result = new F_pers_tree_node;
  87.  
  88.   f_mblack(result);
  89.   result->ver_stamp = i;
  90.   f_lchild(result) = f_rchild(result) = result;
  91.   result->poin_value = newvalue;
  92.   return(result);
  93. }
  94.  
  95. C_pers_tree_node * pers_rb_tree::c_nleaf(int newvalue, Version i)
  96. {
  97.   C_pers_tree_node* result = new C_pers_tree_node;
  98.  
  99.   c_mblack(result);
  100.   result->vers_stamp = i;
  101.   c_lchild(result) = c_rchild(result) = result;
  102.   result->col_value = newvalue;
  103.   return(result);
  104. }
  105.  
  106. F_pers_tree_node * pers_rb_tree::f_nnode(F_pers_tree_node* c1, F_pers_tree_node* c2)
  107. {
  108.   F_pers_tree_node* result = new F_pers_tree_node;
  109.  
  110.   f_mred(result);
  111.   if (vless(c1->ver_stamp, c2->ver_stamp))
  112.   {
  113.     f_lchild(result) = c1;
  114.     c1->f_right = 0;
  115.     f_rchild(result) = c2;
  116.     c2->f_right = 1;
  117.   }
  118.   else
  119.   {
  120.     f_lchild(result) = c2;
  121.     c2->f_right = 0;
  122.     f_rchild(result) = c1;
  123.     c1->f_right = 1;
  124.   }
  125.   f_parent(c1) = f_parent(c2) = result;
  126.   result->ver_stamp = (f_lchild(result))->ver_stamp;
  127.   result->poin_value = NULL;
  128.   return(result);
  129. }
  130.  
  131. C_pers_tree_node* pers_rb_tree::c_nnode(C_pers_tree_node* c1, C_pers_tree_node* c2)
  132. {
  133.   C_pers_tree_node* result = new C_pers_tree_node;
  134.  
  135.   c_mred(result);
  136.   if (vless(c1->vers_stamp, c2->vers_stamp))
  137.   {
  138.     c_lchild(result) = c1;
  139.     c1->c_right = 0;
  140.     c_rchild(result) = c2;
  141.     c2->c_right = 1;
  142.   }
  143.   else
  144.   {
  145.     c_lchild(result) = c2;
  146.     c2->c_right = 0;
  147.     c_rchild(result) = c1;
  148.     c1->c_right = 1;
  149.   }
  150.   c_parent(c1) = c_parent(c2) = result;
  151.   result->vers_stamp = (c_lchild(result))->vers_stamp;
  152.   result->col_value = 0;  
  153.   return(result);
  154. }
  155.  
  156. void  pers_rb_tree::f_single_rot(F_pers_tree_node* top_node, int dir)
  157. {
  158.   F_pers_tree_node *temp, *q;
  159.  
  160.   q = top_node->f_link[1-dir];
  161.   top_node->f_link[1-dir] = temp = q->f_link[dir];
  162.   temp->f_right = 1 - dir;
  163.   f_parent(temp) = top_node;
  164.   q->f_link[dir] = top_node;
  165.   temp = f_parent(top_node);
  166.   f_parent(top_node) = q;
  167.   q->f_right = top_node->f_right;
  168.   temp->f_link[top_node->f_right] = q;
  169.   f_parent(q) = temp;
  170.   top_node->f_right = dir;
  171.   return;
  172. }
  173.  
  174. void  pers_rb_tree::c_single_rot(C_pers_tree_node* top_node, int dir)
  175. {
  176.   C_pers_tree_node *temp, *q;
  177.  
  178.   q = top_node->c_link[1-dir];
  179.   top_node->c_link[1-dir] = temp = q->c_link[dir];
  180.   temp->c_right = 1 - dir;
  181.   c_parent(temp) = top_node;
  182.   q->c_link[dir] = top_node;
  183.   temp = c_parent(top_node);
  184.   c_parent(top_node) = q;
  185.   q->c_right = top_node->c_right;
  186.   temp->c_link[top_node->c_right] = q;
  187.   c_parent(q) = temp;
  188.   top_node->c_right = dir;
  189.   return;
  190. }
  191.  
  192.  
  193. void  pers_rb_tree::f_double_rot(F_pers_tree_node* top_node, int dir)
  194. {
  195.   F_pers_tree_node *q, *r, *temp;
  196.  
  197.   q = top_node->f_link[1-dir];
  198.   r = q->f_link[dir];
  199.   top_node->f_link[1-dir] = temp = r->f_link[dir];
  200.   temp->f_right = 1 - dir;
  201.   f_parent(temp) = top_node;
  202.   q->f_link[dir] = (temp = r->f_link[1-dir]);
  203.   temp->f_right = dir;
  204.   f_parent(temp) = q;
  205.   temp = f_parent(top_node);
  206.   r->f_right = top_node->f_right;
  207.   r->f_link[dir] = top_node;
  208.   f_parent(top_node) = r;
  209.   top_node->f_right = dir;
  210.   r->f_link[1-dir] = q;
  211.   f_parent(q) = r;
  212.   temp->f_link[r->f_right] = r;
  213.   f_parent(r) = temp;
  214.   return;
  215. }
  216.  
  217. void  pers_rb_tree::c_double_rot(C_pers_tree_node* top_node, int dir)
  218. {
  219.   C_pers_tree_node *q, *r, *temp;
  220.  
  221.   q = top_node->c_link[1-dir];
  222.   r = q->c_link[dir];
  223.   top_node->c_link[1-dir] = temp = r->c_link[dir];
  224.   temp->c_right = 1 - dir;
  225.   c_parent(temp) = top_node;
  226.   q->c_link[dir] = (temp = r->c_link[1-dir]);
  227.   temp->c_right = dir;
  228.   c_parent(temp) = q;
  229.   temp = c_parent(top_node);
  230.   r->c_right = top_node->c_right;
  231.   r->c_link[dir] = top_node;
  232.   c_parent(top_node) = r;
  233.   top_node->c_right = dir;
  234.   r->c_link[1-dir] = q;
  235.   c_parent(q) = r;
  236.   temp->c_link[r->c_right] = r;
  237.   c_parent(r) = temp;
  238.   return;
  239. }
  240.  
  241.  
  242. int pers_rb_tree::f_insert(F_pers_tree_node* head, pers_tree_node* newvalue, Version i)
  243. {
  244.   int aux_bool;
  245.   F_pers_tree_node *p, *q, *r, *aux_node;
  246.  
  247.   if (f_rchild(head) == NULL)
  248.   {
  249.     p = f_nleaf(newvalue, i);
  250.     p->f_right = 1;
  251.     f_parent(p) = head;
  252.     f_rchild(head) = p;
  253.     return(0);
  254.   }
  255.   p = f_rbsearch(head, i);
  256.   if (p->ver_stamp == i)
  257.   {
  258.     p->poin_value = newvalue;
  259.     return(1);
  260.   }
  261.   q = f_nleaf(newvalue, i);
  262.   aux_bool = p->f_right;
  263.   aux_node = f_parent(p);
  264.   r = f_nnode(p, q);
  265.   f_parent(r) = aux_node;
  266.   r->f_right = aux_bool;
  267.   aux_node->f_link[aux_bool] = r;
  268.   if (!f_isred(aux_node))
  269.   {
  270.     f_mblack(f_rchild(head));
  271.     return(0);
  272.   }
  273.   q = aux_node;
  274.   p = f_parent(q);
  275.   while ((f_isred(f_lchild(p))) && (f_isred(f_rchild(p))))
  276.   {
  277.     f_mblack(f_lchild(p));
  278.     f_mblack(f_rchild(p));
  279.     f_mred(p);
  280.     r = p;
  281.     q = f_parent(r);
  282.     if (!f_isred(q))
  283.     {
  284.       f_mblack(f_rchild(head));
  285.       return(0);
  286.     }
  287.     p = f_parent(q);
  288.   }
  289.   if (q->f_right == r->f_right)
  290.   {
  291.     f_mred(p);
  292.     f_mblack(q);
  293.     f_single_rot(p, 1-r->f_right);
  294.   }
  295.   else
  296.   {
  297.     f_mblack(r);
  298.     f_mred(p);
  299.     f_double_rot(p, r->f_right);
  300.   }
  301.   f_mblack(f_rchild(head));
  302.   return(0);
  303. }
  304.  
  305. int pers_rb_tree::c_insert(C_pers_tree_node* head, int newvalue, Version i)
  306. {
  307.   int aux_bool;
  308.   C_pers_tree_node *p, *q, *r, *aux_node;
  309.  
  310.   if (c_rchild(head) == NULL)
  311.   {
  312.     p = c_nleaf(newvalue, i);
  313.     p->c_right = 1;
  314.     c_parent(p) = head;
  315.     c_rchild(head) = p;
  316.     return(0);
  317.   }
  318.   p = c_rbsearch(head, i);
  319.   if (p->vers_stamp == i)
  320.   {
  321.     p->col_value = newvalue;
  322.     return(1);
  323.   }
  324.   q = c_nleaf(newvalue, i);
  325.   aux_bool = p->c_right;
  326.   aux_node = c_parent(p);
  327.   r = c_nnode(p, q);
  328.   c_parent(r) = aux_node;
  329.   r->c_right = aux_bool;
  330.   aux_node->c_link[aux_bool] = r;
  331.   if (!c_isred(aux_node))
  332.   {
  333.     c_mblack(c_rchild(head));
  334.     return(0);
  335.   }
  336.   q = aux_node;
  337.   p = c_parent(q);
  338.   while ((c_isred(c_lchild(p))) && (c_isred(c_rchild(p))))
  339.   {
  340.     c_mblack(c_lchild(p));
  341.     c_mblack(c_rchild(p));
  342.     c_mred(p);
  343.     r = p;
  344.     q = c_parent(r);
  345.     if (!c_isred(q))
  346.     {
  347.       c_mblack(c_rchild(head));
  348.       return(0);
  349.     }
  350.     p = c_parent(q);
  351.   }
  352.   if (q->c_right == r->c_right)
  353.   {
  354.     c_mred(p);
  355.     c_mblack(q);
  356.     c_single_rot(p, 1-r->c_right);
  357.   }
  358.   else
  359.   {
  360.     c_mblack(r);
  361.     c_mred(p);
  362.     c_double_rot(p, r->c_right);
  363.   }
  364.   c_mblack(c_rchild(head));
  365.   return(0);
  366. }
  367.  
  368.  
  369.  
  370. /* insert the new version in the appropriate position and update the 
  371.  * version list
  372.  */
  373.  
  374. void pers_rb_tree::del_version(Version) 
  375. { if (--v_list->count ==0) del_tree(); }
  376.  
  377. Version pers_rb_tree::copy_version(Version i) { return new_version(i); }
  378.  
  379. Version pers_rb_tree::new_version(Version i)
  380. {
  381.  
  382.   Version succ = v_list->vl.succ(i);
  383.   
  384.   ver_node p = new VER_pers_tree_node;
  385.  
  386.   if (succ != nil)
  387.      p->ser_num = (v_list->vl[i]->ser_num + v_list->vl[succ]->ser_num) / 2.0;
  388.   else 
  389.      p->ser_num = v_list->vl[i]->ser_num + 1000;
  390.  
  391.  
  392.   p->popul = v_list->vl[i]->popul;
  393.   p->acc_pointer = v_list->vl[i]->acc_pointer;
  394.   v_list->count++;
  395.   return v_list->vl.insert(p,i);
  396. }
  397.  
  398. /* implementation of the update step (change of left or right child)
  399.  * for a specific persistent node and update operation 
  400.  */
  401.  
  402. void pers_rb_tree::update(F_pers_tree_node* p, pers_tree_node* newvalue, Version i)
  403. { 
  404.   F_pers_tree_node *p1, *i1, *i2;
  405.  
  406.   Version ip = v_list->vl.succ(i);
  407.  
  408.   if (f_insert(p, newvalue, i) == 1) return;
  409.  
  410.   if (ip == nil || vless(ip,p->ver_stamp)) return;
  411.  
  412.   p1 = f_rbsearch(p, i);
  413.   if (p1->f_right)
  414.   {
  415.     i1 = f_lchild(f_parent(p1));
  416.     if (f_isleaf(i1))
  417.       goto la;
  418.     else
  419.       i1 = f_rchild(i1);
  420. la: while (p1 != f_rchild(p) && p1->f_right)
  421.       p1 = f_parent(p1);
  422.     if (p1 == f_rchild(p))
  423.       i2 = NULL;
  424.     else
  425.     {
  426.       i2 = f_rchild(f_parent(p1));
  427.       while (!f_isleaf(i2))
  428.         i2 = f_lchild(i2);
  429.     }
  430.   }
  431.   else
  432.   {
  433.     i2 = f_rchild(f_parent(p1));
  434.     if (f_isleaf(i2))
  435.       goto m;
  436.     else
  437.       i2 = f_lchild(i2);
  438.  m: while (p1->f_right == 0)
  439.       p1 = f_parent(p1);
  440.     i1 = f_lchild(f_parent(p1));
  441.     while (!f_isleaf(i1))
  442.       i1 = f_rchild(i1);
  443.   }
  444.   if (i2 == NULL || vless(ip, i2->ver_stamp))
  445.      f_insert(p, i1->poin_value, ip);
  446. }
  447.    
  448.  
  449. /* implementation of the update step (change of color) for a specific
  450.  * persistent node and update operation 
  451.  */
  452.  
  453. void pers_rb_tree::up_col(C_pers_tree_node* p, int newvalue, Version i)
  454. { 
  455.   C_pers_tree_node *p1, *i1, *i2;
  456.   
  457.   Version ip = v_list->vl.succ(i);
  458.  
  459.   if (c_insert(p, newvalue, i) == 1) return;
  460.  
  461.   if (ip ==nil  || vless(ip,p->vers_stamp)) return;
  462.  
  463.   p1 = c_rbsearch(p, i);
  464.   if (p1->c_right)
  465.   {
  466.     i1 = c_lchild(c_parent(p1));
  467.     if (c_isleaf(i1))
  468.       goto lb;
  469.     else
  470.       i1 = c_rchild(i1);
  471. lb: while (p1 != c_rchild(p) && p1->c_right)
  472.       p1 = c_parent(p1);
  473.     if (p1 == c_rchild(p))
  474.       i2 = NULL;
  475.     else
  476.     {
  477.       i2 = c_rchild(c_parent(p1));
  478.       while (!c_isleaf(i2))
  479.         i2 = c_lchild(i2);
  480.     }
  481.   }
  482.   else
  483.   {
  484.     i2 = c_rchild(c_parent(p1));
  485.     if (c_isleaf(i2))
  486.       goto ma;
  487.     else
  488.       i2 = c_lchild(i2);
  489. ma: while (p1->c_right == 0)
  490.       p1 = c_parent(p1);
  491.     i1 = c_lchild(c_parent(p1));
  492.     while (!c_isleaf(i1))
  493.       i1 = c_rchild(i1);
  494.   }
  495.   if (i2 == NULL || vless(ip, i2->vers_stamp))
  496.      c_insert(p, i1->col_value, ip);
  497. }
  498.    
  499.  
  500. /* implementation of the access step for a specific persistent node 
  501.  * and version 
  502.  */
  503.  
  504. pers_tree_node * pers_rb_tree::acc_step(F_pers_tree_node *head, Version i)
  505. {
  506.   F_pers_tree_node *q, *i1;
  507.  
  508.   q = f_rbsearch(head, i);
  509.   if (q->ver_stamp == i)
  510.     return(q->poin_value);
  511.   if (vless(q->ver_stamp, i))
  512.     return(q->poin_value);
  513.   if (q->f_right)
  514.   {
  515.      i1 = f_lchild(f_parent(q));
  516.      if (f_isleaf(i1))
  517.        goto t;
  518.      else
  519.        i1 = f_rchild(i1);
  520.   }
  521.   else
  522.   {
  523.     while (q->f_right == 0)
  524.       q = f_parent(q);
  525.     i1 = f_lchild(f_parent(q));
  526.     while (!f_isleaf(i1))
  527.       i1 = f_rchild(i1);
  528.   }
  529. t:return(i1->poin_value);
  530. }
  531.   
  532.  
  533.  
  534. /* find out whether a given persistent node is red or not in a 
  535.  * specific version 
  536.  */
  537.  
  538. int pers_rb_tree::isred(pers_tree_node* p, Version i)
  539. {
  540.   C_pers_tree_node *head, *q, *i1;
  541.   
  542.   if (isleaf(p))
  543.     return(0);
  544.   head = p->red;
  545.   q = c_rbsearch(head, i);
  546.   if (q->vers_stamp == i)
  547.     return(q->col_value);
  548.   if (vless(q->vers_stamp, i))
  549.     return(q->col_value);
  550.   if (q->c_right)
  551.   {  
  552.      i1 = c_lchild(c_parent(q));
  553.      if (c_isleaf(i1))
  554.        goto s;
  555.      else
  556.        i1 = c_rchild(i1);
  557.   }
  558.   else
  559.   {
  560.     while (q->c_right == 0)
  561.       q = c_parent(q);
  562.     i1 = c_lchild(c_parent(q));
  563.     while (!c_isleaf(i1))
  564.       i1 = c_rchild(i1);
  565.   }
  566. s:return(i1->col_value);
  567. }
  568.  
  569.  
  570. /* create a new leaf and initialize the fields with the appropriate values */
  571.  
  572. pers_tree_node* pers_rb_tree::newleaf(void* val, void* inf, pers_tree_node* pred, pers_tree_node* succ, Version i)
  573. {
  574.   pers_tree_node *result;
  575.   F_pers_tree_node *res1, *res2;
  576.   C_pers_tree_node *res3;
  577.   
  578.   result = new pers_tree_node;
  579.   res1   = new F_pers_tree_node;
  580.   res2   = new F_pers_tree_node;
  581.   res3   = new C_pers_tree_node;
  582.    
  583.     result->key = val;
  584.     result->info = inf;
  585.     result->parent = NULL;
  586.     result->right = 1;
  587.     result->is_leaf = 1;
  588.     result->copy = NULL;
  589.  
  590.     result->next = v_list->used;
  591.     v_list->used = result;
  592.  
  593.     res1->ver_stamp = res2->ver_stamp = res3->vers_stamp = i;
  594.  
  595.     f_lchild(res1) = f_rchild(res1) = f_parent(res1) = NULL;
  596.     f_lchild(res2) = f_rchild(res2) = f_parent(res2) = NULL;
  597.     c_lchild(res3) = c_rchild(res3) = c_parent(res3) = NULL;
  598.  
  599.     res1->f_right = res2->f_right = res3->c_right = 1;
  600.     res1->f_color = res2->f_color = res3->c_color = 0;
  601.  
  602.     res1->poin_value = res2->poin_value = NULL; 
  603.     res3->col_value = 0;  
  604.  
  605.     f_insert(res1, pred, i);
  606.     f_insert(res2, succ, i);
  607.     c_insert(res3, 0, i);
  608.  
  609.     result->link[0] = res1;
  610.     result->link[1] = res2;
  611.     result->red     = res3;
  612.  
  613.     return result;
  614. }
  615.  
  616. /* create a new persistent node and initialize its fields with the
  617.  * appropriate values 
  618.  */
  619.  
  620. pers_tree_node* pers_rb_tree::newnode(pers_tree_node* c1, pers_tree_node* c2, Version i)
  621. {
  622.   // c1 and c2 are leaves
  623.  
  624.   pers_tree_node *result;
  625.   F_pers_tree_node *res1, *res2,  *res4;   // s.n. : res4 pointer to leaf (copy)
  626.   C_pers_tree_node *res3;
  627.   
  628.   result = new pers_tree_node;
  629.   res1   = new F_pers_tree_node;
  630.   res2   = new F_pers_tree_node;
  631.   res3   = new C_pers_tree_node;
  632.   res4   = new F_pers_tree_node;
  633.  
  634.     result->parent = NULL;
  635.  
  636.     result->next = v_list->used;
  637.     v_list->used = result;
  638.  
  639.     res1->ver_stamp = res2->ver_stamp = res3->vers_stamp = i;
  640.  
  641.     f_lchild(res1) = f_rchild(res1) = f_parent(res1) = NULL;
  642.     f_lchild(res2) = f_rchild(res2) = f_parent(res2) = NULL;
  643.     f_lchild(res4) = f_rchild(res4) = f_parent(res4) = NULL;
  644.     c_lchild(res3) = c_rchild(res3) = c_parent(res3) = NULL;
  645.  
  646.     res1->f_right = res2->f_right = res3->c_right = res4->f_right = 1;
  647.     res1->f_color = res2->f_color = res3->c_color = res4->f_color = 0;
  648.  
  649.     res1->poin_value = res2->poin_value = res4->poin_value = NULL; 
  650.     res3->col_value = 1;  
  651.  
  652.     c_insert(res3, 1, i);
  653.  
  654.     if (cmp_keys(c1->key, c2->key) < 1)
  655.     {
  656.       f_insert(res1, c1, i);
  657.       f_insert(res2, c2, i);
  658.       f_insert(res4, c1, i);
  659.       result->key = c1->key;
  660.     }
  661.     else
  662.     {
  663.       f_insert(res1, c2, i);
  664.       f_insert(res2, c1, i);
  665.       f_insert(res4, c2, i);
  666.       result->key = c2->key;
  667.     }
  668.  
  669.     result->link[0] = res1;
  670.     result->link[1] = res2;
  671.     result->red     = res3;
  672.     result->copy    = res4;
  673.     result->is_leaf = 0;
  674.  
  675.     return(result);
  676. }
  677.  
  678.   
  679. /* implementation of the single rotation for the fully persistent
  680.  * red-black tree
  681.  */
  682.  
  683. pers_tree_node* pers_rb_tree::single_rot(pers_tree_node* top_node, int dir, Version i)
  684. {
  685.   pers_tree_node *temp, *q, *newroot;
  686.   
  687.   newroot = NULL;
  688.   q = child(1 - dir, top_node, i);
  689.   temp = child(dir, q, i);
  690.   update(top_node->link[1 - dir], temp, i);
  691.   update(q->link[dir], top_node, i);
  692.   if ((temp = top_node->parent) == NULL)
  693.     newroot = q;
  694.   top_node->parent = q;
  695.   if (temp != NULL)
  696.     update(temp->link[top_node->right], q, i);
  697.   top_node->right = dir;
  698.   return(newroot);
  699. }
  700.  
  701. /* implementation of the double rotation for the fully persistent
  702.  * red-black tree
  703.  */
  704.  
  705. pers_tree_node* pers_rb_tree::double_rot(pers_tree_node* top_node, int dir, Version i)
  706. {
  707.   pers_tree_node *q, *r, *temp, *newroot;
  708.   
  709.   newroot = NULL;
  710.   q = child(1 - dir, top_node, i);
  711.   r = child(dir, q, i);
  712.   temp = child(dir, r, i);
  713.   update(top_node->link[1 - dir], temp, i);
  714.   temp = child(1 - dir, r, i);
  715.   update(q->link[dir], temp, i);
  716.   if ((temp = top_node->parent) == NULL)
  717.     newroot = r;
  718.   update(r->link[dir], top_node, i);
  719.   update(r->link[1 - dir], q, i);
  720.   if (temp != NULL)
  721.     update(temp->link[top_node->right], r, i);
  722.   return(newroot);
  723. }
  724.  
  725. /* the root is colored black after each  update operation */
  726.  
  727. void pers_rb_tree::m_b_root(Version i)
  728. {
  729.   pers_tree_node *p;
  730.  
  731.   p = v_list->vl[i]->acc_pointer;
  732.  
  733.   if (p != NULL && !isleaf(p) && isred(p, i))
  734.      up_col(p->red, 0, i);
  735. }
  736.  
  737.  
  738.  
  739.  
  740. //------------------------------------------------------------------------------
  741. // member functions
  742. //------------------------------------------------------------------------------
  743.  
  744.  
  745. void pers_rb_tree::init_tree()
  746. {
  747.    /* create dummy (empty) version 0 */
  748.    ver_node v = new VER_pers_tree_node;
  749.    v->ser_num =  0;
  750.    v->popul   =  0;
  751.    v->acc_pointer = NULL;
  752.    v_list = new V_LIST;
  753.    v_list->vl.append(v);
  754.    v_list->count = 1;
  755.  
  756.    v_list->used = NULL;
  757.  
  758. }
  759.  
  760. pers_tree_node* pers_rb_tree::search(void *val, pers_tree_node*& copy, Version i)
  761. {
  762.   pers_tree_node *p, *q;
  763.  
  764.   copy = NULL;
  765.   
  766.   if ((p = v_list->vl[i]->acc_pointer) == NULL)
  767.     return(NULL);
  768.  
  769.   p->parent = NULL;
  770.   p->right = 1;
  771.   while (!isleaf(p))
  772.   {
  773.     int v = cmp_keys(val, get_key(p,i));
  774.  
  775.     if (v < 1)
  776.     { if (v==0) copy = p;
  777.       q = p;
  778.       p = child(0, p, i);
  779.       p->parent = q;
  780.       p->right = 0;
  781.      }
  782.     else
  783.     { q = p;
  784.       p = child(1, p, i);
  785.       p->parent = q;
  786.       p->right = 1;
  787.      }
  788.    }
  789.  
  790.    return p;
  791. }
  792.  
  793.  
  794.  
  795. Version  pers_rb_tree::del(void *val, Version i1)
  796. {
  797.   pers_tree_node *pos_del, *par1, *par2, *root, *newroot, *temp, *copy;
  798.  
  799.   Version i  = new_version(i1);
  800.   
  801.   if ((pos_del = search(val, copy, i1)) == NULL) return i; //empty tree
  802.  
  803.   if (cmp_keys(pos_del->key, val) != 0) return i;  // key not found
  804.  
  805.  
  806.   if ((--(v_list->vl[i]->popul)) == 0)
  807.   {
  808.     v_list->vl[i]->acc_pointer = NULL;
  809.     return i;
  810.   }
  811.  
  812.  
  813.   //update links to neighbor leaves
  814.  
  815.   pers_tree_node* pred = child(0,pos_del,i);
  816.   pers_tree_node* succ = child(1,pos_del,i);
  817.  
  818.   if (pred) update(pred->link[1],succ,i);
  819.   if (succ) update(succ->link[0],pred,i);
  820.  
  821.  
  822.   root = v_list->vl[i]->acc_pointer;
  823.  
  824.   if ((par1 = pos_del->parent) == root)
  825.   {
  826.     v_list->vl[i]->acc_pointer = sibling(pos_del, i);
  827.     goto end;
  828.    }
  829.  
  830.   par2 = par1->parent;
  831.   pos_del = sibling(pos_del, i);
  832.   update(par2->link[par1->right], pos_del, i);
  833.   pos_del->parent = par2;
  834.   pos_del->right = par1->right;
  835.  
  836.   if (copy != NULL && copy != par1)  // we have to overwrite copy  by pred
  837.   {
  838.     update(copy->copy, pred, i);
  839.  
  840.    }
  841.   
  842.  
  843.   if (isred(par1, i))
  844.     goto end;
  845.   if (isred(pos_del, i))
  846.   {
  847.     up_col(pos_del->red, 0, i);
  848.     goto end;
  849.   }
  850.   par1 = sibling(pos_del, i);
  851.   while ((!isred(par1, i)) && (!isred(child(0, par1, i), i)) &&
  852.          (!isred(child(1, par1, i), i)))
  853.   {
  854.     up_col(par1->red, 1, i);
  855.     pos_del = pos_del->parent;
  856.     if (isred(pos_del, i))
  857.     {
  858.       up_col(pos_del->red, 0, i);
  859.       goto end;
  860.     }
  861.     if (pos_del == root)
  862.       goto end;
  863.     else
  864.       par1 = sibling(pos_del, i);
  865.   }
  866.   par2 = pos_del->parent;
  867.   if (isred(par1, i))
  868.   {
  869.     up_col(par2->red, 1, i);
  870.     up_col(par1->red, 0,i);
  871.     if ((newroot = single_rot(par2, pos_del->right, i)) != NULL)
  872.       v_list->vl[i]->acc_pointer = newroot;
  873.     par1 = sibling(pos_del,i);
  874.     if ((!isred(child(0, par1, i), i)) && (!isred(child(1, par1, i), i)))
  875.     {
  876.       up_col(par1->red, 1, i);
  877.       up_col((pos_del->parent)->red, 0, i);
  878.       goto end;
  879.     }
  880.   }
  881.   par2 = pos_del->parent;
  882.   if (!pos_del->right)
  883.     if (isred(child(0, par1, i), i))
  884.     {
  885.       temp = child(0, par1, i);
  886.       up_col(temp->red, isred(par2, i), i);
  887.       up_col(par2->red, 0, i);
  888.       newroot = double_rot(par2, LEFT, i);
  889.     }
  890.     else
  891.     {
  892.       up_col(par1->red, isred(par2, i), i);
  893.       up_col(par2->red, 0, i);
  894.       temp = child(1, par1, i);
  895.       up_col(temp->red, 0, i);
  896.       newroot = single_rot(par2, LEFT, i);
  897.     }
  898.   else
  899.     if (isred(child(0, par1, i), i))
  900.     {
  901.       up_col(par1->red, isred(par2, i), i);
  902.       up_col(par2->red, 0, i);
  903.       temp = child(0, par1, i);
  904.       up_col(temp->red, 0, i);
  905.       newroot = single_rot(par2, RIGHT, i);
  906.     }
  907.     else
  908.     {
  909.       temp = child(1, par1, i);
  910.       up_col(temp->red, isred(par2, i), i);
  911.       up_col(par2->red, 0, i);
  912.       newroot = double_rot(par2, RIGHT, i);
  913.     }
  914.   if (newroot != NULL)
  915.     v_list->vl[i]->acc_pointer = newroot;
  916.  
  917. end:
  918.   m_b_root(i);
  919.   return i;
  920. }
  921.  
  922.  
  923. Version pers_rb_tree::insert(void *val, void* info, Version i1)
  924. {
  925.   int aux_bool; 
  926.   pers_tree_node *p, *q, *r, *aux_node, *root, *newroot, *temp;
  927.  
  928.   Version i = new_version(i1);
  929.  
  930.   p = search(val, i1);
  931.  
  932.   if (p && cmp_keys(p->key, val) == 0) return i;  // key already there
  933.  
  934.   copy_key(val);
  935.   copy_inf(info);
  936.   
  937.   if (p == NULL)   // empty tree
  938.   { p = newleaf(val, info, nil, nil, i);
  939.     v_list->vl[i]->acc_pointer = p;
  940.     v_list->vl[i]->popul = 1;
  941.     goto end;
  942.    }
  943.  
  944.   (v_list->vl[i]->popul)++;
  945.  
  946.   if (cmp_keys(val, p->key) > 0)   // new rightmost leaf 
  947.     { q = newleaf(val,info, p, nil, i);   
  948.       update(p->link[1], q, i);
  949.      }
  950.   else // new  leaf before  p 
  951.     { pers_tree_node * pred = child(0,p,i);
  952.       q = newleaf(val,info, pred, p, i);   
  953.       update(p->link[0], q, i);
  954.       if (pred) update(pred->link[1], q, i);
  955.      }
  956.  
  957.   aux_bool = p->right;
  958.   r = newnode(p, q, i);
  959.  
  960.   if (p->parent == NULL)
  961.   {
  962.     v_list->vl[i]->acc_pointer = r;
  963.     goto end;
  964.   }
  965.   aux_node = p->parent;
  966.   r->right = aux_bool;
  967.   update(aux_node->link[aux_bool], r, i);
  968.  
  969.   if (!isred(aux_node, i))
  970.      goto end;
  971.  
  972.   q = aux_node;
  973.   p = q->parent;
  974.   root = v_list->vl[i]->acc_pointer;
  975.   while ((isred(child(0, p, i), i)) && (isred(child(1, p, i), i)))
  976.   {
  977.     temp = child(0, p, i);
  978.     up_col(temp->red, 0, i);
  979.     temp = child(1, p, i);
  980.     up_col(temp->red, 0, i);
  981.     up_col(p->red, 1, i);
  982.     if (p == root)
  983.       goto end;
  984.     r = p;
  985.     q = r->parent;
  986.     if (!isred(q, i))
  987.       goto end;
  988.     p = q->parent;
  989.   }
  990.   if (q->right == r->right)
  991.   {
  992.     up_col(p->red, 1, i);
  993.     up_col(q->red, 0, i);
  994.     newroot = single_rot(p, 1 - r->right, i);
  995.   }
  996.   else
  997.   {
  998.     up_col(r->red, 0, i);
  999.     up_col(p->red, 1, i);
  1000.     newroot = double_rot(p, r->right, i);
  1001.   }
  1002.  
  1003.   if (newroot != NULL)
  1004.     v_list->vl[i]->acc_pointer = newroot;
  1005.  
  1006. end:
  1007.   m_b_root(i);
  1008.   return i;
  1009. }
  1010.  
  1011.  
  1012. Version pers_rb_tree::change_inf(pers_tree_node* p, void* info, Version i1)
  1013. {
  1014.   Version i = new_version(i1);
  1015.  
  1016.   p = search(p->key, i1);  // setting parent pointers
  1017.  
  1018.   pers_tree_node* pred = child(0,p,i);
  1019.   pers_tree_node* succ = child(1,p,i);
  1020.  
  1021.   copy_inf(info);
  1022.   pers_tree_node* q = newleaf(p->key,info, pred, succ, i);   
  1023.  
  1024.  
  1025.   if (pred) update(pred->link[1],q,i);
  1026.   if (succ) update(succ->link[0],q,i);
  1027.  
  1028.   q->right = p->right;
  1029.   update(p->parent->link[q->right], q, i);
  1030.  
  1031.   return i;
  1032.  
  1033. }
  1034.  
  1035.  
  1036.  
  1037. pers_tree_node* pers_rb_tree::min(Version v)
  1038. { pers_tree_node* r = v_list->vl[v]->acc_pointer;
  1039.   if (r == nil) return nil;
  1040.   while ( ! isleaf(r)) r = child(0,r,v);
  1041.   return r;
  1042. }  
  1043.  
  1044. pers_tree_node* pers_rb_tree::max(Version v)
  1045. { pers_tree_node* r = v_list->vl[v]->acc_pointer;
  1046.   if (r == nil) return nil;
  1047.   while ( ! isleaf(r)) r = child(1,r,v);
  1048.   return r;
  1049. }  
  1050.  
  1051. void pers_rb_tree::print(pers_tree_node *p, Version v)
  1052. { if (p)
  1053.   { if (isleaf(p))  
  1054.     { print_key(p->key);
  1055.       cout << " ";
  1056.      }
  1057.     else
  1058.      { print(child(0, p, v), v);
  1059.        print(child(1, p, v), v);
  1060.       }
  1061.    }
  1062. }  
  1063.  
  1064. void pers_rb_tree::del_tree()
  1065. { 
  1066.   while (v_list->used)
  1067.   { pers_tree_node* p = v_list->used;
  1068.     v_list->used = v_list->used->next;
  1069.  
  1070.     f_rbclear(f_rchild(p->link[0]));
  1071.     delete p->link[0];
  1072.  
  1073.     f_rbclear(f_rchild(p->link[1]));
  1074.     delete p->link[1];
  1075.  
  1076.     if (p->copy != nil)
  1077.     {
  1078.       f_rbclear(f_rchild(p->copy));
  1079.       delete p->copy;
  1080.      }
  1081.  
  1082.     c_rbclear(c_rchild(p->red));
  1083.     delete p->red;
  1084.  
  1085.     if (isleaf(p))
  1086.     { clear_key(p->key);
  1087.       clear_inf(p->info);
  1088.      }
  1089.  
  1090.     delete p;
  1091.    }
  1092.  
  1093.    ver_node q;
  1094.    forall(q, v_list->vl) delete q;
  1095.  
  1096.    delete v_list;
  1097.  }  
  1098.  
  1099.  
  1100. pers_tree_node*  pers_rb_tree::lookup(void *val,Version v)
  1101. { pers_tree_node* p = search(val,v);
  1102.   return (p && cmp_keys(key(p), val) == 0) ? p : nil;
  1103.  }
  1104.  
  1105. pers_tree_node* pers_rb_tree::locate(void *val,Version v)
  1106. { pers_tree_node* p = search(val,v);
  1107.   return ( p && cmp_keys(key(p), val) >= 0) ?  p : nil;
  1108.  }
  1109.  
  1110. pers_tree_node* pers_rb_tree::locate_pred(void *val,Version v)
  1111. { pers_tree_node* p = search(val,v);
  1112.   if (p==0) return nil;
  1113.   if (cmp_keys(key(p), val) <= 0)  return p;
  1114.   return child(0,p,v);
  1115.  
  1116. }
  1117.  
  1118.  
  1119.  
  1120.  
  1121. void pers_rb_tree::draw(DRAW_NODE_FCT draw_node,
  1122.                         DRAW_EDGE_FCT draw_edge, 
  1123.                         Version v, pers_tree_node* r, 
  1124.                         double x1, double x2, double y, 
  1125.                         double ydist, double last_x)
  1126. { 
  1127.  
  1128.   double x = (x1+x2)/2;
  1129.  
  1130.   if (r==NULL) return;
  1131.  
  1132.   if (last_x != 0) draw_edge(last_x,y+ydist,x,y);
  1133.  
  1134.   if (isleaf(r)) 
  1135.      draw_node(x,y,r->key);
  1136.   else
  1137.     { draw_node(x,y,get_key(r,v));
  1138.       draw(draw_node,draw_edge,v,child(0,r,v),x1,x,y-ydist,ydist,x);
  1139.       draw(draw_node,draw_edge,v,child(1,r,v),x,x2,y-ydist,ydist,x);
  1140.      }
  1141. }
  1142.  
  1143. void pers_rb_tree::draw(DRAW_NODE_FCT draw_node,
  1144.                         DRAW_EDGE_FCT draw_edge, 
  1145.                         Version v, double x1, double x2, double y, double ydist)
  1146. { draw(draw_node,draw_edge,v,v_list->vl[v]->acc_pointer,x1,x2,y,ydist,0); }
  1147.